This invention relates generally to content addressable memories, sometimes known as associative memories, and relates more particularly to content addressable memories having the ability to store variable length items of information. A content addressable memory includes a memory array in which data items have been stored, and are subsequently accessed by the content of the data items rather than their locations or addresses in the array. An input data item used to access the memory is compared with a large number of the stored data items and a match indication is provided. In many cases the match indication also yields a physical location, which may be used to access related information in a parallel memory structure. For example, if the content addressable memory contains employee badge numbers, a successful matching operation on a desired badge number can be used to access other information in an employee's record.
Most content addressable memories are capable of performing only fixed length comparisons, or a limited selection of fixed length comparisons, where the limited selection includes match lengths that are a subset of the longest available match word. For example, a content addressable memory (CAM) may have a 48-bit word size and be able to perform searches on words of less than 48 bits, but only by masking out the unused bits in each word, using a "don't care" indicator. It is obviously wasteful to use a large memory word in this way to hold a smaller amount of useful information.
The need to store words of various lengths in a CAM is particularly acute in the computer networking field. Various network protocols allow 16-bit, 32-bit and 48-bit station or node addresses, and some allow variable length addresses as large as 160 bits. To accommodate all of these possibilities in a conventional CAM would be costly in the extreme.
Some early CAM designs proposed handling variable length data. For example, U.S. Pat. No. 3,257,646, issued in the name of Robert I. Roth, proposed a scheme in which the beginning and the end of each data word were designated by special characters, and the beginning and end of each field within a word was designated by another special character. A comparator using a complex system of shift registers was used to permit data words and fields to straddle physical word boundaries in the CAM.
There is clearly still room for improvement in the field of CAMs for handling variable length data. The present invention is directed to this end.